#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <stdio.h>
#include <algorithm>
#include <cstdlib>
#include <time.h>

class BinaryTree
{
public:
	BinaryTree()
		: root(0) 
	{
	}

	virtual ~BinaryTree()
	{
		deleteData(root);
	}

	void insertRandomData(const unsigned size)
	{
		srand((unsigned)time(NULL));

		for(unsigned i = 0; i < size; ++i)
			insert(rand() % 10000 / 10.0f);
		
		if(size > 0)
			printf("amount of data: %u, height: %u\n", size, height(root));
		else
			printf("no data\n");
	}
        
	void insert(double d) 
	{
		if (!root) 
			root = new Node(d);
		else insert(root, d);
	}
    
	void print() const 
	{ 
		print(root); 
	}

protected:
    struct Node 
	{
        Node(double d) 
			: data(d), left(0), right(0) 
		{  
		}

        double data;
        Node *left, *right;
    }; 

    void print(Node *node) const 
	{
        if (!node) return;
        print(node->left);
        printf("%.2f (%d)\n", node->data, height(node));
        print(node->right);
    }

    unsigned height(Node *node) const 
	{
        if (!node) 
			return 0;

        return 1 + std::max(height(node->left), height(node->right));
    }

    virtual void insert(Node* &node, double d) 
	{
        if (!node) 
			node = new Node(d);
        if (d < node->data)
			insert(node->left, d);
        else if (d > node->data) 
			insert(node->right, d);
    }

    Node *root;

private:
	void deleteData(Node *node)
	{
		if(node == 0)
			return;

		deleteData(node->left);
		deleteData(node->right);

		delete node;
		node = 0;
	}
};
#endif